package com.mamingchao.basic.arraysort.buckesort.radixsort;

import com.mamingchao.basic.arraysort.Sortable;

/**
 * 基数排序，是桶排序的一种
 * 第一步，基于桶排序思想，按数组里数字的个位排序；
 *    0    1    2   3    4    5     6
 * |    |    |    |    |    |    |     |
 * |    |    |    |    |    |    |     |
 *
 * 第二步，按十位数字，对原数组进行桶排序
 * ......以此类推；比如，数组里数字最长是5位，那么就递归执行5次
 *
 * MSD 的实现
 *
 * Created by mamingchao on 2021/6/22.
 */
public class RadixSort1Impl implements Sortable{

    @Override
    public void sort(int[] arr, int start, int end) {

    }

    /**
     *
     * @param arr 原始数组
     * @param limit 数据 基数值（不重复的数据个数）
     */
    public static void digitCountsort(int[] arr,int limit){
        int[] count = new int[limit];

        //第一层 生成count 数组
        for (int i = 0; i < arr.length; i++) {
            count[arr[i]] ++;
        }

        // 第二层 生成累加数组
        for (int i = 1; i < limit; i++) {
            count[i] = count[i] + count[i-1];
        }


        //倒序遍历原始数组
        int[] sortedArr = new int[arr.length];

        for (int i = arr.length-1; i > 0; i--) {
            sortedArr[count[arr[i]]-1] = arr[i];
            count[arr[i]] --;
        }

        digitCountsort(sortedArr,10);
    }

}
